package com.ztom.top100;

/**
 * 下一个排列
 * <p>
 * https://leetcode-cn.com/problems/next-permutation/
 *
 * @author ZhangTao
 */
public class Code15NextPermutation {

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        // 找到第一个 nums[i] < nums[i + 1] 的位置
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            // 找到 nums[i] < nums[j] 且最小的数(最靠右)的位置 j
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        // 将 i 位置后续的数升序排序
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int i) {
        int l = i;
        int r = nums.length - 1;
        while (l < r) {
            swap(nums, l, r);
            l++;
            r--;
        }
    }

    private void swap(int[] nums, int l, int r) {
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
}
